class Solution:
    def LCS(self, word1: str, word2: str) -> int:
        #The longest common subsequence
        #寻找最长公共子序列 使用dp方法
		#dp[i][j]代表 word1前i个字符和word2前j个字符公共的长度
		#如果dp[i][j], dp[i+1][j], dp[i][j+1] 那么dp[i+1][j+1]就可以推得
		#注意dp[0][0]代表空串的比较, 结果为0
		#不会说会有遗漏的， 因为是一个逐步填充的过程
		#dp[i][]这一行是word1[1]这个字符和word2所有字符比较的过程

        slen1 = len(word1)
        slen2 = len(word2)
        
        if not( slen1!=0 and slen2!=0 ):
            return 0
        
        dp = [ [0 for _ in range(slen2+1)] for _ in range(slen1+1) ]
        
        for idx1 in range(1, slen1+1):
            for idx2 in  range(1, slen2+1):
                if word1[idx1-1] == word2[idx2-1]:
                    dp[idx1][idx2] = dp[idx1-1][idx2-1]+1
                else:
                    dp[idx1][idx2] = max( dp[idx1-1][idx2], dp[idx1][idx2-1] )
        
        LCS = dp[slen1][slen2]
        return LCS